#include <bits/stdc++.h>

using namespace std;

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/the-number-of-beautiful-subsets/solutions/2177818/tao-lu-zi-ji-xing-hui-su-pythonjavacgo-b-fcgs/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public:
        int beautifulSubsets(vector<int>& nums, int k) {
            // f[i] = f[i] + f[i-1](2^{c_i} - 1)    (n[i]-n[i-1] == k)
            // f[i] = f[i](2^{c_i})                 (n[i]-n[i-1] != k)
            unordered_map<int, int> cnt;
            for (int x : nums) {
                cnt[x]++;
            }
    
            int ans = 1;
            for (auto& [x, c] : cnt) {
                if (cnt.count(x - k)) { // x 不是等差数列的首项
                    continue;
                }
                // 计算这一组的方案数
                int f0 = 1, f1 = 1 << c;
                for (int y = x + k; cnt.count(y); y += k) {
                    int new_f = f1 + f0 * ((1 << cnt[y]) - 1);
                    f0 = f1;
                    f1 = new_f;
                }
                ans *= f1; // 每组方案数相乘
            }
            return ans - 1; // 去掉空集
        }
    };
    
